
from collections import Counter, defaultdict


class Solution:

    def minWindow(self, s:str, t:str) -> str:

        cnt_s = Counter()
        cnt_t = Counter(t)
        # cnt_t = defaultdict(int)
        # for c in t:
        #     cnt_t[c] += 1
        # print(len(cnt_t))
        # print(cnt_t)
        ans_left, ans_right = -1, len(s)
        left = 0
        for right, c in enumerate(s):
            cnt_s[c] += 1
            # 会重复出现很多次覆盖窗口
            while cnt_s >= cnt_t:
                # 找到更短的覆盖子串
                if right - left < ans_right - ans_left:
                    ans_left, ans_right = left, right
                
                cnt_s[s[left]] -= 1
                left += 1

        if ans_left < 0:
            return ""
        return s[ans_left: ans_right + 1]
        


if __name__ == "__main__":
    s = "ADOBECODEBANC"
    t = "ABC"

    sol = Solution()
    res = sol.minWindow(s, t)
    print(res)

